package LeetCode.month01.day17;

public class No215 {
    //大根堆排序
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length-1;
        int heapsize = nums.length;
        BuildMaxHeap(nums,heapsize);
        for (int i = 0;i<k-1;i++) {
            swap(nums,0,n-i);
            heapsize--;
            maxHeapify(nums,heapsize,0);
        }
        return nums[0];
    }

    public void BuildMaxHeap(int[] nums,int heapsize){
        for (int i = heapsize/2-1; i >=0; i--) {
            maxHeapify(nums,heapsize,i);
        }
    }

    public void maxHeapify(int[]nums,int heapsize,int i){
        int l = i*2+1;
        int r = i*2+2;
        int largest = i;
        if(l<heapsize&&nums[l]>nums[largest]) largest = l;
        if(r<heapsize&&nums[r]>nums[largest]) largest = r;
        if(largest!=i) {
            swap(nums,largest,i);
            maxHeapify(nums,heapsize,largest);
        }
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]= temp;
    }


    //快速排序
//    public int findKthLargest(int[] nums, int k) {
//        int n = nums.length;
//        return quickSearch(nums,0,n-1,n-k);
//    }
//
//    public int quickSearch(int[] nums,int left,int right, int k){
//        if(left==right) return nums[k];
//        int mid = left+(right-left)/2;
//        int i = left-1;
//        int j = right+1;
//        int x = nums[left];
//        while(i<j){
//            do i++; while(nums[i]<x);
//            do j--; while(nums[j]>x);
//            if(i<j){
//                int temp = nums[i];
//                nums[i] = nums[j];
//                nums[j] = temp;
//            }
//        }
//        if(k>j) return quickSearch(nums,j+1,right,k);
//        else return quickSearch(nums,left,j,k);
//    }
}
